Types are used by programming languages to determine whether a particular data is in a particular form. Conventional programming languages define type systems having types such as integer, string, etc., and user-defined structures. XQuery is a programming language that defines a rich and complicated type system. XQuery is a language for querying XML documents. In addition to types found in conventional programming languages, the type system of languages like XQuery allows new types to be created using sequences (e.g., integer followed by string), alteration (e.g., integer or string), shuffle-product (e.g., integer and string in either order), and occurrences of those (zero or one, zero or more, and one or more).
Types are used by XQuery to determine whether XML data is in the required form. To determine the type of a XML data for atomic types, an XQuery processor can use a class hierarchy to model the type hierarchy as defined in the XQuery specification. For example, the built in or atomic types like xs:integer, xs:boolean, xs:date, etc. can be represented by singleton instances of classes comprising an inheritance hierarchy. FIG. 1 shows such a declaration for an abstract base class XQueryAtomicType with some details of method and data members. Complex types can be created from atomic types. For example XQuery allows complex types to be created from atomic types using sequences, alternation, shuffle-product, occurrences etc. Determining complex types requires type system answering questions like: “If two types are equal?”, “Is one type a subset of another?”, “Do two types intersect?” etc. Using the class hierarchy, it is not sufficient to answer the questions needed to determine complex types.